#pragma once

#include <stdio.h>

void Print(int* array, int size)
{
  for(int i = 0; i < size; i++){
    printf("%d ", array[i]);
  }
  printf("\n");
}

void Swap(int* pa1, int* pa2)
{
  int tmp = *pa1;
  *pa1 = *pa2;
  *pa2 = tmp;
}

void AdjustUp(int* array, int child)
{
  int parent = (child - 1) >> 1;
  while(child > 0){
    if(array[child] > array[parent]) Swap(&array[parent], &array[child]);
    else break;

    child = parent;
    parent = (parent - 1) >> 1;
  }
}

void AdjustDown(int* array, int parent, int end)
{
  int child = (parent << 1) + 1;
  while(child < end){
    if(child + 1 < end &&  array[child] < array[child + 1]) child ++;
    if(array[child] > array[parent]) Swap(&array[child], &array[parent]);
    else break;

    parent = child;
    child = (child << 1) + 1;
  }
}

void HeapSort(int* array, int size)
{
  //向下调整建堆
  //for(int i = (size - 2) >> 1; i>= 0; i--){
  //  AdjustDown(array, i, size);
  //}
  //向上调整建堆
  for(int i = 1; i < size; i++){
    AdjustUp(array, size - i);
  }

  for(int i = 0; i < size; i++){
    Swap(&array[0], &array[size - i - 1]);
    AdjustDown(array, 0, size - i - 1);
  }
}
